package com.sheng.leetcode.year2023.month08.day25;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/8/25
 * <p>
 * 1448. 统计二叉树中好节点的数目<p>
 * <p>
 * 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。<p>
 * 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。<p>
 * <p>
 * 示例 1：<p>
 * 输入：root = [3,1,4,3,null,1,5]<p>
 * 输出：4<p>
 * 解释：图中蓝色节点为好节点。<p>
 * 根节点 (3) 永远是个好节点。<p>
 * 节点 4 -> (3,4) 是路径中的最大值。<p>
 * 节点 5 -> (3,4,5) 是路径中的最大值。<p>
 * 节点 3 -> (3,1,3) 是路径中的最大值。<p>
 * <p>
 * 示例 2：<p>
 * 输入：root = [3,3,null,4,2]<p>
 * 输出：3<p>
 * 解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。<p>
 * <p>
 * 示例 3：<p>
 * 输入：root = [1]<p>
 * 输出：1<p>
 * 解释：根节点是好节点。<p>
 * <p>
 * 提示：<p>
 * 二叉树中节点数目范围是 [1, 10^5] 。<p>
 * 每个节点权值的范围是 [-10^4, 10^4] 。<p>
 */
public class LeetCode1448 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(3, new TreeNode(1, new TreeNode(3), null), new TreeNode(4, new TreeNode(1), new TreeNode(5)));
//        TreeNode root = new TreeNode(3, new TreeNode(3, new TreeNode(4), new TreeNode(2)), null);
        TreeNode root = new TreeNode(1);
        System.out.println(new Solution().goodNodes(root));
    }
}

class Solution {

    int ans = 0;

    public int goodNodes(TreeNode root) {
        dfs(root, root.val);
        return ans;
    }

    public void dfs(TreeNode root, int max) {
        if (root == null) {
            return;
        }
        if (root.val >= max) {
            ans++;
            max = root.val;
        }
        dfs(root.left, max);
        dfs(root.right, max);
    }
}


// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

